package com.fanshuai.algorithms.dynamic;

import org.apache.commons.lang3.StringUtils;

import java.util.ArrayList;
import java.util.List;

/**
 * KMP算法  经典的单模式匹配算法，将字符串匹配复杂度降到o(n)
 * 设主字符串S，模式串P，指针i和j分别指向S和P, KMP算法不必回退i指针，遇到不匹配时，只回退j指针即可
 *
 * 实现原理：
 * 当S[i]!=P[j]时，寻找k指针，使得P[0 .. k-1]=P[j-k .. j-1]，然后j指针回退到k, k为next指针
 * 模式串P的next指针只跟模式串p有关，跟主串S无关。因此设置next数组，使得next[j]=k, P[0 .. k-1]=P[j-k .. j-1]
 *
 * 如果求next数组呢？
 * 我们可以用P字符串匹配P字符串，从前往后遍历，即可求出next数组。设指针j指向当前位置，指针k指向next[j]，初始化j=0, k=-1
 *
 * 1 next[0] = -1, 因为索引0前面没有字符了
 * 2 next[1] = 0,  当P[1]不匹配时，j指针回退到0
 *
 * 3 若P[j] = P[k]，则next[j + 1] = next[j] + 1; 假设next[j]=k, 则P[0 .. k-1] = P[j-k .. j-1]，由于P[j]=P[k]，所以
 * P[0 .. k] = P[j-k .. j]，因此next[j+1] = k+1 = next[j] + 1
 *
 * 4 如果P[j] != P[k]，则k需要回退到next[k]位置。设next[k]=k0, P[0 .. k0] = P[k-k0 .. k-1]
 */
public class KMP {
    /**
     * 求next数组
     * @param p
     * @return
     */
    private static int[] getNext(String p) {
        char[] charArr = p.toCharArray();

        int[] next = new int[charArr.length];
        next[0] = -1;

        int j = 0, k = -1;
        while (j < charArr.length - 1) {
            if (k == -1 || charArr[j] == charArr[k]) { //k==-1 或P[j] = P[k], 则next[j + 1] = next[j] + 1
                next[++j] = ++k;
            } else {
                k = next[k]; //P[j] != P[k]，则k需要回退到next[k]位置
            }
        }

        return next;
    }

    /**
     * KMP算法
     * @param s  主字符串
     * @param p  模式串
     * @return  返回p的索引
     */
    public static int KMP(String s, String p) {
        int[] next = getNext(p);

        int i = 0, j = 0;
        while (i < s.length() && j < p.length()) {
            if (j == -1 || s.charAt(i) == p.charAt(j)) { //s[i]和p[j]相等，指针往后移。或p[0]和s[i]不匹配时，指针后移
                i++;
                j++;
            } else {
                j = next[j];  //s[i]和p[j]不匹配，指针回退到next[j]
            }
        }

        if (j == p.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    /**
     * 字符串匹配  返回多个索引
     * @param s
     * @param p
     * @return
     */
    public static List<Integer> MultiKmp(String s, String p) {
        int[] next = getNext(p);

        List<Integer> indices = new ArrayList<>();

        int i = 0, j = 0;
        while (i < s.length()) {
            if (j == -1 || s.charAt(i) == p.charAt(j)) { //s[i]和p[j]相等，指针往后移
                i++;
                j++;
            } else {
                j = next[j];  //s[i]和p[j]不匹配，指针回退到next[j]
            }

            if (j == p.length()) {
                indices.add(i - j);
                j = 0;
            }
        }

        return indices;
    }

    /**
     * 普通字符串匹配
     * @param s
     * @param p
     * @return
     */
    public static int indexOf(String s, String p) {
        if (StringUtils.isBlank(s) || StringUtils.isBlank(p)) {
            return -1;
        }

        int i = 0, j = 0;
        while (i < s.length()) {
            if (s.charAt(i) == p.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }

            if (j == p.length()) {
                return i - j;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        String p = "abc";

        String s1 = "dhfisdabcudghabcuiqafhabcuiedfh";
        String s2 = "dghfrdgoirgjoghi";

        System.out.println(KMP(s1, p));
        System.out.println(KMP(s2, p));

        System.out.println(MultiKmp(s1, p));
        System.out.println(MultiKmp(s2, p));

        System.out.println(indexOf(s1, p));
        System.out.println(indexOf(s2, p));
    }
}
